package com.ohc.itnanls.tree;

import javax.swing.tree.TreeNode;
import java.util.*;

public class TreeTest {
    public static void bfs(Node root) {
        Queue<Node> queue = new LinkedList<>();//队列实现
        queue.add(root);
        List<List<Integer>> array = new ArrayList<>();//
        while (!queue.isEmpty()) {
            int cnt = queue.size();
            //取出上一层的所有节点，将下一层的所有节点入队
//             cnt判断改成是否结束
            List<Integer> list = new ArrayList<>();
            while (cnt-- > 0) {
                Node node = queue.poll();//取出队首元素
                list.add(node.data);
                System.out.println("node.data = " + node.data);
                System.out.println(node.data);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            array.add(list);
            //一层的遍历结束，可以在此计算树的深度，或者得到此层所有节点
        }
        System.out.println("array.size() = " + array.size());
    }

    public static void bfsStack(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {

            Node node = stack.pop();
            System.out.println("node.data = " + node.data);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    public static void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println("node = " + node.data);
        inOrder(node.right);

    }

    public static class Node {
        public Node() {
        }

        public Node(int data) {
            this.data = data;
        }


        private int data;

        Node left;

        Node right;
    }


    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right = new Node(3);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        bfsStack(root);
    }
}
